package LeetCode.month04.day113;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 16778
 * @date 2025/11/23 8:15
 * @description
 */
public class No1262 {

    //动态规划
    public int maxSumDivThree2(int[] nums) {
        int n = nums.length;
        int[][] memo = new int[n][3];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i],-1);
        }
        return dfs(memo,nums,n-1,0);
    }

    private int dfs(int[][] memo, int[] nums, int i, int j) {
        if(i<0){
            return j==0?0:Integer.MIN_VALUE;
        }
        if(memo[i][j]!=-1) return memo[i][j];
        return memo[i][j]=Math.max(dfs(memo,nums,i-1,j),dfs(memo,nums,i-1,(j+nums[i])%3)+nums[i]);
    }


    //贪心
    public int maxSumDivThree(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        int n = nums.length;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%3==0){
            return sum;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if(nums[i]%3==1){
                list1.add(nums[i]);
            }else if(nums[i]%3==2){
                list2.add(nums[i]);
            }
        }
        if(sum%3==2){
            var temp = list1;
            list1 = list2;
            list2 = temp;
        }
        int ans = list1.isEmpty()?0:sum-list1.get(0);
        if(list2.size()>1){
            ans = Math.max(ans,sum-list2.get(0)-list2.get(1));
        }
        return ans;
    }
}
